package com.hgx.algorithm.base.sort;


import com.hgx.algorithm.base.utils.ArraySortUtil;

/**
 * 快速排序：最常用的排序方法
 * ①代码简洁，实现容易
 * ②复杂度指标一样的时候，常数项小，效率更高，没有额外的空间复杂度
 *
 * 经典快速排序：最好的情况时间复杂度O(N*logN) 最差情况时间复杂度O(N^2)
 * 随机快速排序：和概率有关，通过长期的期望，则时间复杂度为O(N*logN)，额外空间复杂度O(logN)
 *
 * 为了解决数据状况对排序的影响：① 随机 ②hash
 * 稳定性：不稳定（可以做到 很难）
 * 基础数据排序时，工程上首选快排
 */

public class QuickSort {


    public static void main(String[] args) {
        int[] arr = new int[]{1, 7, -10, 9, 0, 0, -16, -3, 6, 1, 7, -12, 0, 34};
        ArraySortUtil.print(arr);
        sort(arr);
        ArraySortUtil.print(arr);
    }

    /**
     * 快速排序
     *
     * @param arr 需要排序的数组
     */
    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序实现
     *
     * @param arr   需要排序的数组
     * @param left  数组左坐标
     * @param right 数组右坐标
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //随机快速排序：随机选一个数为参考值
            ArraySortUtil.swap(arr, left + (int) Math.random() * (right - left + 1), right);
            int[] positions = partition(arr, left, right);
            quickSort(arr, left, positions[0] - 1);
            quickSort(arr, positions[1] + 1, right);
        }

    }

    /**
     * 实现：数组arr，小于arr最右边数的数放在数组的左边，等于arr最右边数的数放在数组的中间，大于arr最右边数的数放在数组的右边。
     *
     * @param arr   需要排序的数组
     * @param left  需要排序段的左边坐标
     * @param right 需要排序段的右1边坐标
     * @return 返回数组中等于number的坐标区域
     */
    public static int[] partition(int[] arr, int left, int right) {
        //小于区域的坐标
        int less = left - 1;
        //大于区域的坐标
        int more = right;
        while (left < more) {
            if (arr[left] < arr[right]) {
                ArraySortUtil.swap(arr, left++, ++less);
            } else if (arr[left] > arr[right]) {
                ArraySortUtil.swap(arr, left, --more);
            } else {
                left++;
            }
        }
        ArraySortUtil.swap(arr, more, right);
        return new int[]{less + 1, more};
    }

}
